package algorithm.middle;

import java.util.TreeMap;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: LongestSubarray1438
 * @description: 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
 *
 * 如果不存在满足条件的子数组，则返回 0 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/2/2314:31
 * @since V1.0
 */
public class LongestSubarray1438 {
    //判断方法会超时
    public int longestSubarray(int[] nums, int limit) {
        int left=0;
        int right=0;
        int res=0;
        out:while (right<nums.length){
            //对是否符合进行标记
            for (int i=0;i<right-left;i++){
                if (Math.abs(nums[right]-nums[left+i])>limit){
                    left=left+i+1;
                    continue out;
                }
            }
            //如果符合
            res=Math.max(res,right-left+1);
            right++;

        }
        return res;
    }

    //滑动窗口 二叉树 TreeMap
    /**
     * 在 Java 中 TreeSet 是有序的去重集合，TreeMap 是 key 有序的哈希表，它们也是基于红黑树实现的。
     * 本题需要保存滑动窗口内的所有元素（可能含有重复元素），可以使用的 C++ 的 multiset/map 与 Java 中的 TreeMap。
     * 当频繁的插入和删除元素时，multiset/map 和 TreeMap 等有序的数据结构能够在在 O(log(k))O(log(k))O(log(k))  的时间复杂度内调整 BST，从而维护结构的有序性。
     * multiset 和 TreeMap 都提供了获取第一个元素和最后一个元素的函数，也就能在 O(1)O(1)O(1) 的时间内获取滑动窗口内最小值和最大值。
     *
     * 作者：fuxuemingzhu
     * 链接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/he-gua-de-shu-ju-jie-gou-hua-dong-chuang-v46j/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int 官方题解(int[] nums, int limit) {
        TreeMap<Integer, Integer> m = new TreeMap<>();
        int left = 0, right = 0;
        int res = 0;
        while (right < nums.length) {
            m.put(nums[right], m.getOrDefault(nums[right], 0) + 1);
            //一直移动左指针，直到最大值最小值之差符合条件即可
            while (m.lastKey() - m.firstKey() > limit) {
                m.put(nums[left], m.get(nums[left]) - 1);
                if (m.get(nums[left]) == 0) {
                    m.remove(nums[left]);
                }
                left ++;
            }
            res = Math.max(res, right - left + 1);
            right ++;
        }
        return res;
    }

}
